The Halting Problem

Does a program halt?

Definition

There does not exist a program terminates(p, x) that can determine the termination of any program p on input data x.

Proof

• Suppose there is such a program:

  terminates(p, x) = [p halts on x]? TRUE : FALSE

• Then we can construct another program:

  paradox(p) = [¬terminates(p, p)]? TRUE : [loop forever]

• The fact that the termination of paradox(paradox) is a contradiction proves that terminates(p, x) does not exist.

• This tells us programming will never be automated. It will forever depend on discipline, ingenuity, and hackery. We can't tell whether a program has an infinite loop, or buffer overrun, etc.

by Jon